require 'mathn'
require 'set'

module MostUselessStuff
    
    $DEBUG = true
    def MostUselessStuff.assert(*msg)
        raise "Assertion failed! #{msg}" until yield if $DEBUG
    end
    
    def MostUselessStuff.time_elapsed
        t1 = Time.now
        yield
        t2 = Time.now - t1
        puts "time elapsed: #{t2.round(3)}s"
    end
    

    
    class ShidokuSolver
    public
        def solve(area)
            # A * X = B
            # X = A^-1 * B
            
            a = (0..63).collect {Array.new(64, 0)}
            ma = Matrix.rows(a, false)
            
            b = (0..63).collect {Array.new(1, 0)}
            mb = Matrix.rows(b, false)
            
            _init_ab(area, a, b, ma)
#            puts 'ma = ' + ma.inspect
#            puts 'mb = ' + mb.inspect
            
            if ma.rank == 64
                mx = ma.inverse * mb
#               puts 'mx=' + mx.inspect
            
                x = mx.to_a
                
                sol = (0..3).collect {Array.new(4, 0)}
            
                sol.each_index do |i|
                    sol[i].each_index do |j|
                        sol[i][j] = 1 if x[16*0 + i * 4 + j][0] == 1
                        sol[i][j] = 2 if x[16*1 + i * 4 + j][0] == 1
                        sol[i][j] = 3 if x[16*2 + i * 4 + j][0] == 1
                        sol[i][j] = 4 if x[16*3 + i * 4 + j][0] == 1
                    end
                end
            else
                puts 'too difficult'
            end
            return sol
        end
         
    protected
        
        def _init_ab(area, a, b, ma)
#            MostUselessStuff.assert {(ma * ma.transpose).trace == 0}
#            MostUselessStuff.assert {ma.rank == 0}
            
            
            row = -1
            #---------------------
            #one unique number per row, column and block
            # rows
            (0..15).each do |i|
                v = i * 4 
                a[row += 1].one(v, v+1, v+2, v+3) 
                b[row][0] = 1
            end
            
            # cols
            [0, 16, 32, 48].each do |i|
                (0..2).each do |j|
                    v = i + j
                    a[row += 1].one(v, v+4, v+8, v+12)
                    b[row][0] = 1
                end
            end
            
            # blocks
            [0, 16, 32, 48].each do |i|
                a[row += 1].one(i, i+1, i+4, i+5)
                b[row][0] = 1
            end
            
#            MostUselessStuff.assert {ma.rank == 32}
            
            #--------------------
            # every number occupies its own cell
            [0, 1, 2, 4, 6, 8, 9, 10].each do |i|
                a[row += 1].one(i, i+16, i+32, i+48)
                b[row][0] = 1
            end

#            MostUselessStuff.assert {ma.rank == 40}


            #---------------------
            # known numbers (at least 4 numbers)
            
            area.each_index do |i|
                area[i].each_index do |j|
                    v = area[i][j] 
                    if v > 0
                        index = i*4 + j
                        s = (v-1)*16
                        inds = Set.new 
                        inds << s+i*4 << s+i*4+1 << s+i*4+2 << s+i*4+3 << s+j << s+j+4 << s+j+8
                        inds << s + index << index << index + 16 << index + 32
                        prev = ma.rank
                        inds.each do |ind|
#                            MostUselessStuff.assert {row != 63 or (row == 63 and prev == 64)}
                            break if row == 63
                            a[row += 1].one(ind)
                            b[row][0] = ind == (index + s) ? 1 : 0
                            curr = ma.rank
                            if prev == curr 
                                a[row][ind] = 0
                                b[row][0] = 0
                                row -= 1
                            end
                            prev = curr
                        end
                    end
                end
            end

#            puts "rank = #{ma.rank}"
#            MostUselessStuff.assert {ma.rank == 64}
            
            #puts a.inspect
        end

    end
end

class Array
    def one(*indices)
        indices.each do |index| self[index] = 1; end
    end
end

#################################

area = [[1, 0, 4, 0],
        [0, 0, 2, 1],
        [0, 0, 0, 2],
        [0, 3, 0, 0]]
MostUselessStuff.time_elapsed {
    puts 'area = ' + area.inspect
    solution = MostUselessStuff::ShidokuSolver.new.solve(area)
    puts 'solution = ' + solution.inspect
}

MostUselessStuff.time_elapsed {
    m = Matrix.zero(700)
    (0..200).each do m.rank; end
}